/*
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。

你可以 任意多次交换 在 pairs 中任意一对索引处的字符。

返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

 

示例 1:

输入：s = "dcab", pairs = [[0,3],[1,2]]
输出："bacd"
解释： 
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"
示例 2：

输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出："abcd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"
示例 3：

输入：s = "cba", pairs = [[0,1],[1,2]]
输出："abc"
解释：
交换 s[0] 和 s[1], s = "bca"
交换 s[1] 和 s[2], s = "bac"
交换 s[0] 和 s[1], s = "abc"
 

提示：

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s 中只含有小写英文字母

*/

#include "stdc++.h"

/* 并查集
既然可以任意地交换通过「索引对」直接相连的字符，那么我们也任意地交换通过「索引对」间接相连的字符。
我们利用这个性质将该字符串抽象：将每一个字符抽象为「点」，那么这些「索引对」即为「边」，我们只需要维护这个「图」的连通性即可。
对于同属一个连通块（极大连通子图）内的字符，我们可以任意地交换它们。
这样我们的思路就很清晰了：利用并查集维护任意两点的连通性，将同属一个连通块内的点提取出来，直接排序后放置回其在字符串中的原位置即可。
*/
class DisjointSetUnion {
public: // 不相交集合
    DisjointSetUnion(int n) {
        rank.resize(n, 1);
        f.resize(n, 0);
        for (int i{0}; i < n; ++i) {
            f[i] = i;
        }
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void unionSet(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            if (rank[fx] < rank[fy]) {
                swap(fx, fy);
            }
            rank[fx] += rank[fy];
            f[fy] = fx;
        }
    }
private:
    vector<int> f;
    vector<int> rank;
};
class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.length();
        DisjointSetUnion dsu(n);
        for (auto& it : pairs) {
            dsu.unionSet(it[0], it[1]);
        }
        unordered_map<int, vector<int>> mp{};
        for (int i{0}; i < n; ++i) {
            mp[dsu.find(i)].emplace_back(s[i]);
        }
        for (auto& it : mp) {
            auto& vec = it.second;
            sort(vec.begin(), vec.end(), greater<int>());
        }
        // C++17
        // for (auto& [x, vec] : mp) {
        //     sort(vec.begin(), vec.end(), greater<int>());
        // }
        for (int i{0}; i < n; ++i) {
            int x = dsu.find(i);
            s[i] = mp[x].back();
            mp[x].pop_back();
        }
        return s;
    }
};